package main;

/**
 * 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 * <p>
 * 示例：
 * 输入：(2 -> 4 ->  ) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 */
public class LeetCode2 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int addflag = 0;
        ListNode result = new ListNode(0);
        ListNode result_ptr = result;
        while (l1 != null || l2 != null || addflag != 0) {  // 当 l1,l2不全为null或者addflag不为0时继续
            if (l1 == null && l2 != null) {  // l1结束
                result_ptr.val = l2.val + addflag;
                addflag = 0;
                if (result_ptr.val >= 10) {  // 若result_ptr.val 大于10,则 result_ptr.val -10 且 addflag++ 进位
                    result_ptr.val = result_ptr.val - 10;
                    addflag++;
                }
                l2 = l2.next;
                ListNode next = new ListNode(0);
                result_ptr.next = next;
                result_ptr = result_ptr.next;
                continue;
            }
            if (l2 == null && l1 != null) {  // l2 结束
                result_ptr.val = l1.val + addflag;
                addflag = 0;
                if (result_ptr.val >= 10) {  // 若result_ptr.val 大于10,则 result_ptr.val -10 且 addflag++ 进位
                    result_ptr.val = result_ptr.val - 10;
                    addflag++;
                }
                l1 = l1.next;
                ListNode next = new ListNode(0);
                result_ptr.next = next;
                result_ptr = result_ptr.next;
                continue;
            }
            if (addflag != 0 && l1 == null) {  // 当addflag不为0 且 l1,l2全为null时
                result_ptr.val = result_ptr.val + addflag;
                addflag = 0;
                if (result_ptr.val >= 10) {  // 若result_ptr.val 大于10,则 result_ptr.val -10 且 addflag++ 进位
                    result_ptr.val = result_ptr.val - 10;
                    addflag++;
                }
                ListNode next = new ListNode(0);
                result_ptr.next = next;
                result_ptr = result_ptr.next;
                continue;
            }
            // l1,l2均未结束
            if ((l1.val + l2.val) >= 10) {  // l1.val + l2.val 大于10 addflag++ 表示进位
                result_ptr.val = (l1.val + l2.val + addflag - 10);
                addflag = 0;   // addflag使用后应立即置0
                addflag++;
                if (result_ptr.val >= 10) {  // 若result_ptr.val 大于10,则 result_ptr.val -10 且 addflag++ 进位
                    result_ptr.val = result_ptr.val - 10;
                    addflag++;
                }
            } else {
                result_ptr.val = l1.val + l2.val + addflag;
                addflag = 0; // addflag使用后应立即置0
                if (result_ptr.val >= 10) {  // 若result_ptr.val 大于10,则 result_ptr.val -10 且 addflag++ 进位
                    result_ptr.val = result_ptr.val - 10;
                    addflag++;
                }
            }
            l1 = l1.next;
            l2 = l2.next;
            ListNode next = new ListNode(0);
            result_ptr.next = next;
            result_ptr = result_ptr.next;
        }
        result_ptr = result;
        while (true) {
            if (result_ptr.next.next != null || result_ptr.next.val != 0) {  // 遍历去掉最后一个多余的节点
                result_ptr = result_ptr.next;
            } else {
                result_ptr.next = null;
                break;
            }
        }
        return result;
    }

    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {  // 官方解题
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        LeetCode2 leetCode2 = new LeetCode2();
        ListNode l1 = new ListNode(5);
//        ListNode l1_ptr = l1;
//        l1_ptr.next = new ListNode(4);
//        l1_ptr = l1_ptr.next;
//        l1_ptr.next = new ListNode(3);

        ListNode l2 = new ListNode(5);
//        ListNode l2_ptr = l2;
//        l2_ptr.next = new ListNode(6);
//        l2_ptr = l2_ptr.next;
//        l2_ptr.next = new ListNode(4);
        ListNode result = leetCode2.addTwoNumbers(l1, l2);
        while (result != null) {
            System.out.print(result.val);
            result = result.next;
        }
    }

}
